题目大意
来自：https://shenjie1993.gitbooks.io/leetcode-python/068%20Text%20Justification.html
把一个集合的单词按照每行L个字符存放，不足的在单词间添加空格，每行要两端对齐(即两端都要是单词)，如果空格不能均匀分布在所有间隔中，那么左边的空格要多于右边的空格，最后一行靠左对齐，每个单词间一个空格。
注意点：
单词的顺序不能发生改变
中间行也可能出现只有一个单词，这时要靠左对齐
每行要尽可能多的容纳单词
解题思路
参考：https://shenjie1993.gitbooks.io/leetcode-python/068%20Text%20Justification.html
采用双指针的方法来标记当前行的单词，如果加上下一个单词的长度和每个单词间至少一个空格时的总长度大于目标长度，说明此时的单词就是该行应该存放的。要分是否只有一个单词还是多个单词进行讨论，如果有多个单词，需要平均分配单词间的空格。现在可以知道总的空格数和单词间隔数，所以计算单词间的间隔比较简单，注意多余的空格要优先添加到左边的单词间隔中。不要忘记添加最后一行的单词。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
start = end = 0
result, curr_words_length = [], 0
for i, word in enumerate(words):
if len(word) + curr_words_length + end - start > maxWidth:
if end - start == 1:
result.append(words[start] + ' ' * (maxWidth - curr_words_length))
else:
total_space = maxWidth - curr_words_length
space, extra = divmod(total_space, end - start - 1)
for j in range(extra):
words[start + j] += ' '
result.append((' ' * space).join(words[start:end]))
curr_words_length = 0
start = end = i
end += 1
curr_words_length += len(word)
result.append(' '.join(words[start:end]) + ' ' * (maxWidth - curr_words_length - (end - start - 1)))
return result
|
总结
自己写了很久，测试集24个通过16个，卡在了单词中自带/符号的，太坑了，不写了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
if words == ['']:
return [' ' * maxWidth]
result = []
word_temp = []
length_temp = 0
length_each_temp = 0
string = ''
for i, word in enumerate(words):
word_temp.append(word)
length_temp += len(word)+1
print i, word
print word_temp, length_temp
if length_temp > maxWidth+1:
word_use = word_temp[:-1]
print 'word_use', word_use
if len(word_use) == 1:
result.append(word_use[0] + ' ' * (maxWidth-len(word_use[0])))
elif len(word_use) == 2:
result.append(word_use[0] + ' ' * (maxWidth-(len(word_use[0])+len(word_use[1]))) + word_use[1])
else:
for each_word in word_use:
length_each_temp += len(each_word)
print 'length_each_temp', length_each_temp
space_num = maxWidth - length_each_temp
print 'space_num', space_num
space = space_num // 2
print 'space', space
if space_num % 2 == 1: # 不均匀
string += word_use[0] + ' ' * (space+1)
print string
for j in range(1, len(word_use)):
string += word_use[j] + ' ' * space
print string
else:
for each_word in word_use:
string += each_word + ' ' * space
print 'string', len(string), string
if space:
string = string[:-space]
result.append(string)
word_temp = word_temp[-1:]
length_temp = len(word_temp[0]) + 1
length_each_temp = 0
string = ''
print '----------'
if word_temp:
for word in word_temp:
string += word + ' '
result.append(string + ' ' * (maxWidth-len(string)))
if len(result[-1]) != maxWidth:
result[-1] = result[-1][:maxWidth]
return result
|